import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

class MyCompare implements Comparator<Integer> {
    @Override
    public int compare(Integer o1, Integer o2){
        return o2.compareTo(o1);
    }
}
public class TestHeap {
    private int elem[];
    private int usedSize;

    public TestHeap() {
        elem = new int[10];
    }

    public int[] getElem() {
        return elem;
    }

    public void setElem(int[] elem) {
        this.elem = elem;
    }

    public int getUsedSize() {
        return usedSize;
    }

    public void setUsedSize(int usedSize) {
        this.usedSize = usedSize;
    }
    public boolean isFull(){
        return usedSize == elem.length;
    }
    public boolean isEmpty(){
        return usedSize == 0;
    }
    public void init(int[] array){
        for(int x : array){
            if(isFull())
                elem = Arrays.copyOf(elem, elem.length*2);
            elem[usedSize++] = x;
        }
    }
    public void swap(int x, int y){
        int tmp = elem[x];
        elem[x] = elem[y];
        elem[y] = tmp;
    }
    public void bigSiftDown(int parent, int end){
        int child = parent*2+1;
        while(child < end){
            if(child+1 < end && elem[child] < elem[child+1])
                child++;
            if(elem[parent] < elem[child]) {
                swap(parent, child);
                parent = child;
                child = parent*2+1;
            }
            else{
                break;
            }
        }
    }
    //创建大根堆
    public void createdBigHeap(){
        for(int parent = (usedSize-2)/2; parent >= 0; parent--){
            bigSiftDown(parent, usedSize);
        }
    }
    public void bigSiftUp(int child){
        int parent = (child-1)/2;
        while(parent >= 0){
            if(elem[child] > elem[parent]){
                swap(child, parent);
                child = parent;
                parent = (child-1) / 2;
            }
            else{
                break;
            }
        }
    }
    //添加一个数依旧保持大根堆
    public void offerBig(int val){
        if(isFull())
            elem = Arrays.copyOf(elem, 2*elem.length);
        elem[usedSize++] = val;
        bigSiftUp(usedSize-1);
    }
    //删除一个数依旧保持大根堆
    public int pollBig(){
        if(isEmpty())
            return -1;
        int old = elem[0];
        swap(0,usedSize-1);
        usedSize--;
        bigSiftDown(0, usedSize);
        return old;
    }
    //获取第k小的数
    public int kMinHeap(int[] arr, int k){
        if(k == 0)
            return -1;
        PriorityQueue<Integer> bigHeap = new PriorityQueue<>(new MyCompare());
        for(int i = 0; i < k; i++){
            bigHeap.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            int val = bigHeap.peek();
            if(val > arr[i]){
                bigHeap.poll();
                bigHeap.offer(arr[i]);
            }
        }
        return bigHeap.peek();
    }
    //获取前k个小的数
    public int[] kMinHeapArr(int[] arr, int k){
        int[] tmp = new int[k];
        if(k == 0)
            return tmp;
        PriorityQueue<Integer> bigHeap = new PriorityQueue<>(new MyCompare());
        for(int i = 0; i < k; i++){
            bigHeap.offer(arr[i]);
        }
        for (int i = k; i < arr.length; i++) {
            int val = bigHeap.peek();
            if(val > arr[i]){
                bigHeap.poll();
                bigHeap.offer(arr[i]);
            }
        }
        for (int i = 0; i < k; i++) {
            tmp[i] = bigHeap.poll();
        }
        return tmp;
    }
    //堆排序--从小到大
    public void heapSort(){
        int endIndex = usedSize-1;
        while(endIndex > 0){
            swap(0, endIndex);
            bigSiftDown(0, endIndex);
            endIndex--;
        }
    }

    public void smallSiftDown(int parent, int end){
        int child = parent*2+1;
        while(child < usedSize){
            if(child+1 < usedSize && elem[child] > elem[child+1])
                child++;
            if(elem[parent] > elem[child]) {
                swap(parent, child);
                parent = child;
                child = parent*2+1;
            }
            else{
                break;
            }
        }
    }
    //创建小根堆
    public void createdSmallHeap(){
        for(int parent = (usedSize-2)/2; parent >= 0; parent--){
            smallSiftDown(parent, usedSize);
        }
    }
    public void smallSiftUp(int child){
        int parent = (child-1)/2;
        while(parent >= 0){
            if(elem[child] < elem[parent]){
                swap(child, parent);
                child = parent;
                parent = (child-1) / 2;
            }
            else{
                break;
            }
        }
    }
    //添加一个数依旧保持小根堆
    public void offerSmall(int val){
        if(isFull())
            elem = Arrays.copyOf(elem, 2*elem.length);
        elem[usedSize++] = val;
        smallSiftUp(usedSize-1);
    }
    //删除一个数依旧保持小根堆
    public int pollSmall(){
        if(isEmpty())
            return -1;
        int old = elem[0];
        swap(0,usedSize-1);
        usedSize--;
        smallSiftDown(0, usedSize);
        return old;
    }
}
